from typing import List


class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        S = {-1: set()}
        nums.sort()
        for x in nums:
            temp = []
            for d in S:
                print('x==>', x, ',d==>', d)
                if (x % d == 0):
                    # 为了把之前的集合带上
                    S[d].add(x)
                    temp.append(S[d])
                    S[d].remove(x)
            # 之前的集合 加上自身，构成一个新的集合
            S[x] = max(temp, key=len) | {x}
        # 返回最长的数组
        return list(max(S.values(), key=len))
        # return ""


if __name__ == '__main__':
    nums = [1, 2, 4, 8]
    solution = Solution()
    print(solution.largestDivisibleSubset(nums))
